package longestNiceSubstring;

import java.util.HashSet;
import java.util.Set;

public class Solution {
//    public String longestNiceSubstring(String s) {
//        // 枚举 字符串的长度
//        String ans = "";
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = i+1; j <s.length() ; j++) {
//                String t = s.substring(i,j+1);
//                if(check(t)){
//                    if(t.length()>ans.length()){
//                        ans = t;
//                    }
//                }
//            }
//        }
//        return ans;
//    }
//    private boolean check(String s) {
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if(Character.isLowerCase(c)){
//                if(!s.contains(Character.toUpperCase(c)+"")){
//                    return false;
//                }
//            }else {
//                if(!s.contains(Character.toLowerCase(c)+"")){
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
    private int maxPos;
    private int maxLen;
public String longestNiceSubstring(String s) {
    // 分治
    this.maxPos = 0;
    this.maxLen = 0;
    dfs(s,0,s.length()-1);
    return s.substring(maxPos,maxPos+maxLen);
}
// 如果一个字符串是完美字符串 那么一定不包含非法字符（即只有小写或者只有大写）
private void dfs(String s,int start,int end){
    if(start>=end)return;
    int lower = 0,upper = 0;
    for (int i = start; i <= end; i++) {
        if(Character.isLowerCase(s.charAt(i))){
            lower|=1<<(s.charAt(i)-'a');
        } else {
            upper|=1<<(s.charAt(i)-'A');
        }
    }
    if(lower == upper){
        if(end-start+1>maxLen){
            maxPos = start;
            maxLen = end-start+1;
        }
        return;
    }
    int valid = lower & upper;
    int pos = start;
    while (pos <= end) {
        start = pos;
        while (pos <= end && (valid & (1 << Character.toLowerCase(s.charAt(pos)) - 'a')) != 0) {
            ++pos;
        }
        dfs(s, start, pos - 1);
        ++pos;
    }
}
}
